/*
https://leetcode-cn.com/problems/loud-and-rich/solution/xuan-nao-he-fu-you-by-leetcode-solution-jnzm/
 */
import java.util.Arrays;

public class Solution851 {
    public int[] loudAndRich(int[][] richer, int[] quiet) {
        int n=quiet.length;
        int[][] map=new int[n][n];
        for (int[] ints : richer) {
            map[ints[1]][ints[0]]=1;
        }
        int[] ans=new int[n];
        Arrays.fill(ans,-1);
        for (int i = 0; i < n; i++) {
            dfs(i,quiet,map,ans);
        }
        return ans;
    }

    public void dfs(int k,int[] quiet,int[][] map,int[] ans){
        if (ans[k]!=-1){
            return ;
        }else{
            ans[k]=k;
            for (int i=0;i<quiet.length;i++){
                if (map[k][i]==1){
                    dfs(i,quiet,map,ans);
                    if (quiet[ans[i]]<quiet[ans[k]]){
                        ans[k]=ans[i];
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Solution851().loudAndRich(new int[][]{{1,0},{2,1},{3,1},{3,7},{4,3},{5,3},{6,3}},new int[]{3,2,5,4,6,1,7,0})));
    }
}
